In a digital data communication system (including storage and retrieval from electronic memory, optical media or magnetic media) errors may occur as a result of noise, media defects or circuit failure. For reliable communications it is necessary to be reasonably sure of detecting all transmission errors. One way of doing this is by the use of cyclic redundancy check symbols or CRCs. In general CRCs are calculated by treating the data as the coefficients of a polynomial and dividing the data by another polynomial and keeping the remainder. The data and CRC together make up a codeword which is then transmitted into the communication channel. At the receiving end of the channel a CRC is again calculated and compared to the original. A discrepancy between the two CRCs indicates a transmission error.
In some applications the data and CRC together are coded into an error-correcting code by adding error-correcting characters (ECC). After a correction procedure has been used the CRC can be used to detect errors that are either not detected or are miscorrected by the corrector.
The data can be viewed as a sequence of binary bits or a sequence of multi-bit symbols. In general a bit-oriented CRC is desired if the expected errors are random bit errors and a symbol-oriented CRC is desired if the expected errors are burst errors or random symbol errors.
FIG. 1 shows a typical bit-oriented 8-bit CRC generator where the serial input is on the DATA line.
FIG. 2 shows a typical byte-oriented 8-bit CRC generator where D.sub.0 to D.sub.7 make up the input data byte.
FIG. 3 shows a data transmission system which includes a dynamic RAM (DRAM) for temporary storage and a communication channel which could be, for example, magnetic storage. The system uses an ECC system to correct errors occurring in the communication channel. It also employs a two-byte CRC to check for errors in data retrieved from the DRAM and to check the results of the corrector. For ECC purposes the data is partitioned into three interleaves. Each interleave makes up one ECC codeword containing two ECC bytes which can correct one byte in each interleave. This is a common technique for making a system capable of correcting a burst error of three bytes but using an ECC capable of correcting only one byte. Conceptually, during ECC generation, the first data byte goes into ECC generator 1, the second byte goes into ECC generator 2, the third byte goes into ECC generator 3, the fourth byte goes into ECC generator 1, etc. After the data has been input to the generators the first ECC byte comes from the generator which follows the generator which received the last data byte and the remaining ECC bytes are taken from the generators in the same sequence as previously described. All signal lines are 8 bits wide.
The generator in FIG. 1 will generate an 8-bit CRC character which can be used to detect any error which affects at most two bits in the serial data stream. If, however, the input data is the result of serializing a sequence of data bytes, it is not possible to detect every single-byte error.
The generator in FIG. 2 will generate an 8-bit CRC character which can be used to detect any single-byte error. It cannot, however, detect every two-bit error since the two errors could be in two different bytes.
The CRC in FIG. 3 will detect all two-byte errors (and consequently all two-bit errors) in a block of data read from the DRAM. However, regardless of which CRC and ECC polynomials are used it is possible to have three errors in one interleave which are not detected by the ECC or CRC.